package java2d.game.sudoku;

import java.io.File;
import java.io.IOException;
import java.nio.charset.Charset;
import java.nio.file.Files;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

@SuppressWarnings("unused")
public class SudokuModel
{
    public interface Listener
    {
        void puzzleInit();

        void puzzleUpdated();

        void puzzleSolved();

        void puzzleUnsolvable();
    }

    // Cell对于模型之外的对象表现为只读
    public static class Cell
    {
        // row,column是行列索引
        // numbers[0]是确定数，numbers[1~N]是候选数（值等于索引）
        private final int row;
        private final int column;
        private final int[] numbers;
        private final boolean[] candidates;
        private boolean anchor;
        private boolean duplicate;

        Cell(int row, int column, int scale)
        {
            this.row = row;
            this.column = column;
            this.numbers = new int[scale + 1];
            this.candidates = new boolean[scale];
            this.anchor = false;
            this.duplicate = false;
        }

        public int getRow()
        {
            return row;
        }

        public int getColumn()
        {
            return column;
        }

        public int getInput()
        {
            return numbers[0];
        }

        public boolean[] getCandidateMarks()
        {
            if (numbers[0] > 0)
                Arrays.fill(candidates, false);
            else
                for (int i = 0; i < candidates.length; i++)
                    candidates[i] = numbers[i + 1] > 0;
            return candidates;
        }

        public boolean isAnchor()
        {
            return anchor;
        }

        public boolean isDuplicate()
        {
            return duplicate;
        }

        private void reset()
        {
            Arrays.fill(numbers, 0);
            anchor = false;
            duplicate = false;
        }

        private void setInput(int input)
        {
            numbers[0] = input;
        }

        private void setFullCandidates()
        {
            for (int n = 1; n < numbers.length; n++)
                numbers[n] = n;
        }

        private void setCandidates(int... candidates)
        {
            // candidate的值域：[1,numbers.length]
            for (int candidate : candidates)
                numbers[candidate] = candidate;
        }

        private Cell snapshot()
        {
            Cell snapshot = new Cell(row, column, numbers.length);
            System.arraycopy(this.numbers, 0, snapshot.numbers, 0, this.numbers.length);
            snapshot.anchor = this.anchor;
            snapshot.duplicate = this.duplicate;
            return snapshot;
        }

        public String toString()
        {
            if (numbers[0] == 0)
                return " _ ";
            if (anchor)
                return "[" + numbers[0] + "]";
            if (duplicate)
                return "*" + numbers[0] + " ";
            return " " + numbers[0] + " ";
        }
    }

    public enum Difficulty
    {EASY, MEDIUM, HARD, VERY_HARD, EXTREME_HARD, CUSTOM}

    public record Puzzle(Difficulty difficulty, int[][] board, boolean uniqueSolution)
    {
    }

    private record Profile(String name, int scale, int gridCount, int gridRowScale, int gridColumnScale)
    {
    }

    private record Change(int row, int column, int oldNumber, int newNumber)
    {
    }

    private static final Profile PROFILE_TINY = new Profile("tiny", 2, 0, 0, 0);  // 2x2, 没有小网格
    private static final Profile PROFILE_MEDIUM = new Profile("medium", 4, 4, 2, 2);  // 4x4，网格2x2
    private static final Profile PROFILE_STANDARD = new Profile("standard", 9, 9, 3, 3);  // 9x9，网格3x3
    private static final Profile PROFILE_ABNORMITY = new Profile("abnormity", 6, 6, 2, 3);  // 6x6, 网格2x3

    private Profile profile;
    private Cell[][] cells;
    private Cell[][] snapshots;
    private List<Integer> digits;
    private Difficulty difficulty;
    private boolean hasDuplicate;

    private volatile boolean stopGeneration;
    private volatile boolean foundUniqueSolution;

    private final Deque<Change> changes;
    private final List<Listener> listeners;
    private final Random random;

    public static SudokuModel tiny()
    {
        return new SudokuModel(PROFILE_TINY);
    }

    public static SudokuModel medium()
    {
        return new SudokuModel(PROFILE_MEDIUM);
    }

    public static SudokuModel standard()
    {
        return new SudokuModel(PROFILE_STANDARD);
    }

    public static SudokuModel abnormtiy()
    {
        return new SudokuModel(PROFILE_ABNORMITY);
    }

    private SudokuModel(Profile profile)
    {
        this.profile = profile;
        this.cells = new Cell[profile.scale][profile.scale];
        this.snapshots = new Cell[profile.scale][profile.scale];
        this.digits = IntStream.range(1, profile.scale + 1).boxed().toList();
        this.changes = new LinkedList<>();
        this.listeners = new ArrayList<>();
        this.random = new Random();

        this.difficulty = Difficulty.CUSTOM;
        this.foundUniqueSolution = false;

        for (int row = 0; row < profile.scale; row++)
        {
            for (int column = 0; column < profile.scale; column++)
            {
                cells[row][column] = new Cell(row, column, profile.scale);
                snapshots[row][column] = new Cell(row, column, profile.scale);
                snapshots[row][column].setFullCandidates();
            }
        }
    }

    public void addListener(Listener listener)
    {
        if (listener != null)
            listeners.add(listener);
    }

    public void removeListener(Listener listener)
    {
        if (listener != null)
            listeners.remove(listener);
    }

    public Difficulty getDifficulty()
    {
        return difficulty;
    }

    public int getScale()
    {
        return profile.scale;
    }

    public int getGridPerRow()
    {
        return profile.scale / profile.gridColumnScale;
    }

    public int getGridPerColumn()
    {
        return profile.scale / profile.gridRowScale;
    }

    public int getGridRowScale()
    {
        return profile.gridRowScale;
    }

    public boolean hasNumberInGrid(int number, int row, int column)
    {
        int gridStartRI = row * profile.gridRowScale;
        int gridStartCI = column * profile.gridColumnScale;

        for (int r = 0; r < profile.gridRowScale; r++)
            for (int c = 0; c < profile.gridColumnScale; c++)
                if (cells[gridStartRI + r][gridStartCI + c].getInput() == number)
                    return true;
        return false;
    }

    public int getGridColumnScale()
    {
        return profile.gridColumnScale;
    }

    public List<Cell> findCells(int number)
    {
        if (number == 0)
            return Collections.emptyList();

        List<Cell> list = new ArrayList<>();
        for (int row = 0; row < profile.scale; row++)
        {
            for (int column = 0; column < profile.scale; column++)
            {
                Cell cell = cells[row][column];
                if (cell.numbers[0] == number)
                    list.add(cell);
            }
        }
        return list;
    }

    public List<Cell> findCellsWithCandidate(int number)
    {
        if (number == 0)
            return Collections.emptyList();

        List<Cell> list = new ArrayList<>();
        for (int row = 0; row < profile.scale; row++)
        {
            for (int column = 0; column < profile.scale; column++)
            {
                Cell cell = cells[row][column];
                if (cell.numbers[0] == 0 && cell.numbers[number] == number)
                    list.add(cell);
            }
        }
        return list;
    }

    public Cell getCell(int row, int column)
    {
        return cells[row][column];
    }

    public boolean isAnchorCell(int row, int column)
    {
        return cells[row][column].anchor;
    }

    public void setCellInput(int row, int column, int input)
    {
        Cell cell = cells[row][column];
        if (cell.anchor)
            return; // 锚点不可修改

        int oldInput = cell.getInput();
        if (oldInput == input)
            return; // 相同的数字，不做修改

        cell.setInput(input);
        changes.push(new Change(row, column, oldInput, input));

        updateBoardStatus();

        for (Listener listener : listeners)
            listener.puzzleUpdated();
    }

    public void clearCellInput(int row, int column)
    {
        Cell cell = cells[row][column];
        if (cell.anchor)
            return; // 锚点不可修改

        int oldInput = cell.getInput();
        if (oldInput > 0)
        {
            cell.setInput(0);
            changes.push(new Change(row, column, oldInput, 0));

            updateBoardStatus();
            for (Listener listener : listeners)
                listener.puzzleUpdated();
        }
    }

    public boolean[] getCellCandidateMarks(int row, int column)
    {
        boolean[] marks = new boolean[profile.scale];

        Cell cell = cells[row][column];
        for (int i = 0; i < marks.length; i++)
            marks[i] = cell.numbers[i + 1] > 0;

        return marks;
    }

    public void toggleCellCandidate(int row, int column, int number)
    {
        Cell cell = cells[row][column];
        if (cell.anchor)
            return; // 锚点不可修改

        cell.numbers[number] = (cell.numbers[number] == 0) ? number : 0;
        for (Listener listener : listeners)
            listener.puzzleUpdated();
    }

    public void clearCellCandidates(int row, int column)
    {
        Cell cell = cells[row][column];
        if (cell.anchor)
            return; // 锚点不可修改

        Arrays.fill(cell.numbers, 0);
        for (Listener listener : listeners)
            listener.puzzleUpdated();
    }

    public void fillCellCandidates(int row, int column)
    {
        cells[row][column].setFullCandidates();

        updateBoardStatus();
        for (Listener listener : listeners)
            listener.puzzleUpdated();
    }

    public void fillBoardCandidates()
    {
        for (int r = 0; r < profile.scale; r++)
            for (int c = 0; c < profile.scale; c++)
                cells[r][c].setFullCandidates();

        updateBoardStatus();
        for (Listener listener : listeners)
            listener.puzzleUpdated();
    }

    public void rollback()
    {
        Change lastChange = changes.poll();
        if (lastChange != null)
        {
            Cell cell = cells[lastChange.row][lastChange.column];
            cell.setInput(lastChange.oldNumber);

            updateBoardStatus();

            for (Listener listener : listeners)
                listener.puzzleUpdated();
        }
    }

    public void snapshot()
    {
        // 每次设置锚点相当于将当前局面做一次快照，并以当前局面为基础进行初始化。
        // 如果当前局面存在明显的冲突，则停止（拒绝）快照。

        if (hasDuplicate)
            return;

        for (int r = 0; r < profile.scale; r++)
        {
            for (int c = 0; c < profile.scale; c++)
            {
                Cell cell = cells[r][c];
                cell.anchor = (cell.numbers[0] > 0);
                cell.duplicate = false;
                snapshots[r][c] = cell.snapshot();
            }
        }

        changes.clear();

        fillBoardCandidates();
    }

    public void restore()
    {
        // 从快照中恢复
        for (int ri = 0; ri < profile.scale; ri++)
            for (int ci = 0; ci < profile.scale; ci++)
                cells[ri][ci] = snapshots[ri][ci].snapshot();

        changes.clear();
        hasDuplicate = false;

        updateBoardStatus();
        for (Listener listener : listeners)
            listener.puzzleUpdated();
    }

    public void init(Puzzle puzzle)
    {
        if (puzzle.board.length != profile.scale || puzzle.board[0].length != profile.scale)
            throw new IllegalArgumentException("无效的题目");

        this.difficulty = puzzle.difficulty;
        this.foundUniqueSolution = puzzle.uniqueSolution;
        this.hasDuplicate = false;
        for (int ri = 0; ri < profile.scale; ri++)
            for (int ci = 0; ci < profile.scale; ci++)
            {
                cells[ri][ci].reset();
                cells[ri][ci].setInput(puzzle.board[ri][ci]);
            }

        snapshot();

        for (Listener listener : listeners)
            listener.puzzleInit();
    }

    public Puzzle generate(Difficulty difficulty)
    {
        if (difficulty == Difficulty.CUSTOM)
            return new Puzzle(Difficulty.CUSTOM, new int[profile.scale][profile.scale], false);

        double density = switch (difficulty)
        {
            case EXTREME_HARD -> random.nextDouble(0.33, 0.35);
            case VERY_HARD -> random.nextDouble(0.35, 0.38);
            case HARD -> random.nextDouble(0.38, 0.45);
            case MEDIUM -> random.nextDouble(0.45, 0.55);
            case EASY -> random.nextDouble(0.55, 1.0);
            default -> throw new IllegalArgumentException("无效的难度：" + difficulty);
        };

        int[][] board = randomInit();
        int[][] puzzle = new int[profile.scale][profile.scale];
        int holes = (int) (profile.scale * profile.scale * (1 - density));
        stopGeneration = false;
        // 如果外部不终止，则持续找到唯一解。
        while (!stopGeneration)
        {
            for (int ri = 0; ri < profile.scale; ri++)
                System.arraycopy(board[ri], 0, puzzle[ri], 0, profile.scale);

            int count = 0;
            while (count < holes)
            {
                int row = random.nextInt(profile.scale);
                int col = random.nextInt(profile.scale);
                if (puzzle[row][col] != 0)
                {
                    puzzle[row][col] = 0;
                    count++;
                }
            }
            if (hasUniqueSolution(puzzle))
            {
                System.out.println("找到唯一解");
                return new Puzzle(difficulty, puzzle, true);
            }
        }

        System.out.println("没有找到唯一解");
        return new Puzzle(difficulty, puzzle, false);
    }

    public void stopGeneration()
    {
        stopGeneration = true;
    }

    public boolean hasUniqueSolution()
    {
        return foundUniqueSolution;
    }

    public void solve()
    {
        if (hasDuplicate)
        {
            for (Listener listener : listeners)
                listener.puzzleUnsolvable();
            return;
        }

        int[][] snapshot = new int[profile.scale][profile.scale];
        for (int ri = 0; ri < profile.scale; ri++)
            for (int ci = 0; ci < profile.scale; ci++)
                snapshot[ri][ci] = cells[ri][ci].numbers[0];

        boolean hasBlanks = checkBlanks(snapshot);
        if (hasBlanks)
        {
            if (randomSolve(snapshot, 0, 0))
            {
                for (int ri = 0; ri < profile.scale; ri++)
                    for (int ci = 0; ci < profile.scale; ci++)
                        cells[ri][ci].numbers[0] = snapshot[ri][ci];

                snapshot();

                for (Listener listener : listeners)
                    listener.puzzleSolved();
            } else
            {
                for (Listener listener : listeners)
                    listener.puzzleUnsolvable();
            }
        } else
        {
            if (isSolved())
            {
                for (Listener listener : listeners)
                    listener.puzzleSolved();
            } else
            {
                for (Listener listener : listeners)
                    listener.puzzleUnsolvable();
            }
        }
    }

    public void check()
    {
        if (isSolved())
        {
            snapshot();
            for (Listener listener : listeners)
                listener.puzzleSolved();
        }
    }

    public void print()
    {
        for (int r = 0; r < profile.scale; r++)
        {
            for (int c = 0; c < profile.scale; c++)
                System.out.printf("%s ", cells[r][c].numbers[0]);
            System.out.println();
        }
        System.out.println();
    }

    public void load(File archive) throws IOException
    {
        List<String> lines = Files.readAllLines(archive.toPath());
        if (lines.size() < 3)
            throw new IOException("无效的存档");

        Profile archivedProfile = switch (lines.getFirst())
        {
            case "tiny" -> PROFILE_TINY;
            case "medium" -> PROFILE_MEDIUM;
            case "standard" -> PROFILE_STANDARD;
            case "abnormity" -> PROFILE_ABNORMITY;
            default -> null;
        };
        if (archivedProfile == null)
            throw new IOException("无效的存档");

        Difficulty archivedDifficulty;
        boolean archivedUniqueSolution;
        Cell[][] archivedCells = new Cell[archivedProfile.scale][archivedProfile.scale];
        Cell[][] archivedSnapshots = new Cell[archivedProfile.scale][archivedProfile.scale];
        List<Integer> archivedDigits = IntStream.range(1, archivedProfile.scale + 1).boxed().toList();

        try
        {
            archivedDifficulty = Difficulty.valueOf(lines.get(1));
            archivedUniqueSolution = Boolean.parseBoolean(lines.get(2));

            for (int row = 0; row < archivedProfile.scale; row++)
            {
                String line = lines.get(row + 3);
                String[] inputs = line.split("\\s", -1);
                for (int column = 0; column < archivedProfile.scale; column++)
                {
                    Cell cell = new Cell(row, column, archivedProfile.scale);
                    cell.numbers[0] = Integer.parseInt(inputs[column]);
                    cell.anchor = (cell.numbers[0] > 0);
                    cell.duplicate = false;
                    cell.setFullCandidates();

                    archivedCells[row][column] = cell;
                    archivedSnapshots[row][column] = cell.snapshot();
                }
            }
        } catch (Exception any)
        {
            throw new IOException("无效的存档");
        }

        this.profile = archivedProfile;
        this.difficulty = archivedDifficulty;
        this.cells = archivedCells;
        this.snapshots = archivedSnapshots;
        this.digits = archivedDigits;

        changes.clear();
        hasDuplicate = false;
        foundUniqueSolution = archivedUniqueSolution;

        updateBoardStatus();

        for (Listener listener : listeners)
            listener.puzzleInit();
    }

    public void save(File archive) throws IOException
    {
        int[][] board = new int[profile.scale][profile.scale];
        for (int r = 0; r < profile.scale; r++)
        {
            for (int c = 0; c < profile.scale; c++)
            {
                Cell cell = cells[r][c];
                board[r][c] = cell.getInput();
            }
        }

        StringBuilder sbuf = new StringBuilder();
        sbuf.append(profile.name).append(System.lineSeparator());
        sbuf.append(difficulty.name()).append(System.lineSeparator());
        sbuf.append(foundUniqueSolution).append(System.lineSeparator());
        for (int r = 0; r < board.length; r++)
        {
            String row = IntStream.of(board[r]).mapToObj(String::valueOf).collect(Collectors.joining(" "));
            sbuf.append(row).append(System.lineSeparator());
        }
        Files.writeString(archive.toPath(), sbuf.toString(), Charset.defaultCharset());
    }

    private int[][] randomInit()
    {
        int[][] board = new int[profile.scale][profile.scale];
        List<Integer> numbers = new ArrayList<>(digits);
        Collections.shuffle(numbers, random);

        // 随机设置一行，然后随机化求解。
        int r = random.nextInt(profile.scale);
        for (int c = 0; c < profile.scale; c++)
            board[r][c] = numbers.get(c);
        randomSolve(board, 0, 0);
        return board;
    }

    private void updateBoardStatus()
    {
        // 检查盘面数字冲突状态
        // 更新空白单元格的候选数字

        // 故意增加一个空位，省略后续循环中的对索引的减一操作，加快执行速度。
        int[] counter = new int[profile.scale + 1];
        int row, column;

        hasDuplicate = false;
        for (row = 0; row < profile.scale; row++)
            for (column = 0; column < profile.scale; column++)
                cells[row][column].duplicate = false;

        // 逐行检查
        for (row = 0; row < profile.scale; row++)
        {
            Arrays.fill(counter, 0);

            for (column = 0; column < profile.scale; column++)
                updateCounter(cells[row][column], counter);

            for (column = 0; column < profile.scale; column++)
            {
                updateCell(cells[row][column], counter);
                hasDuplicate = hasDuplicate || cells[row][column].duplicate;
            }
        }

        // 逐列检查
        for (column = 0; column < profile.scale; column++)
        {
            Arrays.fill(counter, 0);

            for (row = 0; row < profile.scale; row++)
                updateCounter(cells[row][column], counter);

            for (row = 0; row < profile.scale; row++)
            {
                updateCell(cells[row][column], counter);
                hasDuplicate = hasDuplicate || cells[row][column].duplicate;
            }
        }

        // 逐网格检查
        for (int gr = 0, rows = profile.scale / profile.gridRowScale; gr < rows; gr++)
        {
            for (int gc = 0, columns = profile.scale / profile.gridColumnScale; gc < columns; gc++)
            {
                int gridStartRI = gr * profile.gridRowScale;
                int gridStartCI = gc * profile.gridColumnScale;

                Arrays.fill(counter, 0);
                for (row = 0; row < profile.gridRowScale; row++)
                    for (column = 0; column < profile.gridColumnScale; column++)
                        updateCounter(cells[gridStartRI + row][gridStartCI + column], counter);

                for (row = 0; row < profile.gridRowScale; row++)
                    for (column = 0; column < profile.gridColumnScale; column++)
                    {
                        updateCell(cells[gridStartRI + row][gridStartCI + column], counter);
                        hasDuplicate = hasDuplicate || cells[gridStartRI + row][gridStartCI + column].duplicate;
                    }
            }
        }
    }

    private void updateCounter(Cell cell, int[] counter)
    {
        int input = cell.getInput();

        // 标记已填数
        counter[input] += 1;
    }

    private void updateCell(Cell cell, int[] counter)
    {
        int input = cell.getInput();

        // 当前输入数与同行其它格输入重复，且当前格不是预设值
        cell.duplicate = cell.duplicate || (!cell.anchor && input > 0 && counter[input] > 1);
        if (input > 0)
        {
            // 清空候选数
            for (int n = 1; n <= profile.scale; n++)
                cell.numbers[n] = 0;
        } else
        {
            // 从候选数中删掉已经填入的数
            // 只做减法，不添加新的候选数
            for (int n = 1; n <= profile.scale; n++)
                if (counter[n] > 0)
                    cell.numbers[n] = 0;
        }
    }

    private boolean isSolved()
    {
        if (hasDuplicate)
            return false;

        int sum = 0;
        for (int ri = 0; ri < profile.scale; ri++)
            for (int ci = 0; ci < profile.scale; ci++)
                sum += cells[ri][ci].numbers[0];
        int expect = (1 + profile.scale) * profile.scale / 2 * profile.scale;
        return sum == expect;
    }

    private boolean checkBlanks(int[][] board)
    {
        for (int ri = 0; ri < profile.scale; ri++)
            for (int ci = 0; ci < profile.scale; ci++)
                if (board[ri][ci] == 0)
                    return true;
        return false;
    }

    private boolean randomSolve(int[][] board, int ri, int ci)
    {
        if (ri == profile.scale)
            return true;
        if (ci == profile.scale)
            return randomSolve(board, ri + 1, 0);
        if (board[ri][ci] != 0)
            return randomSolve(board, ri, ci + 1);

        // 增加一点随机性，这样每次求得解可能不一样。
        List<Integer> numbers = new ArrayList<>(digits);
        Collections.shuffle(numbers, random);
        for (int number : numbers)
        {
            if (isValid(board, ri, ci, number))
            {
                board[ri][ci] = number;
                if (randomSolve(board, ri, ci + 1))
                    return true; // 找到解

                // 当前数字导致后续无解，则回溯。
                board[ri][ci] = 0;
            }
        }
        return false; // 所有数字都不合适，回溯
    }

    private boolean hasUniqueSolution(int[][] board)
    {
        int[][] copy = new int[profile.scale][profile.scale];
        for (int ri = 0; ri < profile.scale; ri++)
            System.arraycopy(board[ri], 0, copy[ri], 0, profile.scale);

        int solutions = findUniqueSolution(copy, 0, 0);
        return solutions == 1;
    }

    private int findUniqueSolution(int[][] board, int ri, int ci)
    {
        if (ri == profile.scale)
            return 1;
        if (ci == profile.scale)
            return findUniqueSolution(board, ri + 1, 0);
        if (board[ri][ci] != 0)
            return findUniqueSolution(board, ri, ci + 1);

        int solutions = 0;
        for (int number = 1; number <= profile.scale; number++)
        {
            if (isValid(board, ri, ci, number))
            {
                board[ri][ci] = number;
                solutions += findUniqueSolution(board, ri, ci + 1);
                board[ri][ci] = 0;

                // 这里只是为了求唯一解，所以如果解不唯一，
                // 就立即结束，不作过多纠缠。
                if (solutions > 1)
                    return 2;
            }

            if (stopGeneration)
                return 2;
        }
        return solutions;
    }

    // 检查数字是否可以放置在指定位置
    private boolean isValid(int[][] board, int r, int c, int n)
    {
        // 检查所在行
        for (int i = 0; i < profile.scale; i++)
            if (board[r][i] == n)
                return false;
        // 检查所在列
        for (int i = 0; i < profile.scale; i++)
            if (board[i][c] == n)
                return false;
        // 检查所在网格
        int startRow = r / profile.gridRowScale * profile.gridRowScale;
        int startCol = c / profile.gridColumnScale * profile.gridColumnScale;
        for (int i = 0; i < profile.gridRowScale; i++)
            for (int j = 0; j < profile.gridColumnScale; j++)
                if (board[startRow + i][startCol + j] == n)
                    return false;
        return true;
    }
}
